SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Arithmetic function</title>

</head>

Arithmetic function

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Number_theory" title="Number theory">number theory</a>, an arithmetic, arithmetical, or number-theoretic function<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> is generally any <a href="Function_(mathematics)" title="Function (mathematics)">function</a> whose <a href="Domain_of_a_function" title="Domain of a function">domain</a> is the set of <a href="Natural_number" title="Natural number">positive integers</a> and whose range is a <a href="Subset" title="Subset">subset</a> of the <a href="Complex_number" title="Complex number">complex numbers</a>.<a href="#cite_note-3">[3]</a><a href="#cite_note-4">[4]</a><a href="#cite_note-5">[5]</a> Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".<a href="#cite_note-6">[6]</a> There is a larger class of number-theoretic functions that do not fit this definition, for example, the <a href="Prime-counting_function" title="Prime-counting function">prime-counting functions</a>. This article provides links to functions of both classes.

An example of an arithmetic function is the <a href="Divisor_function" title="Divisor function">divisor function</a> whose value at a positive integer n is equal to the number of divisors of n.

Arithmetic functions are often extremely irregular (see <a href="#First_100_values_of_some_arithmetic_functions">table</a>), but some of them have series expansions in terms of <a href="Ramanujan's_sum" title="Ramanujan's sum">Ramanujan's sum</a>.

<div class="mw-heading mw-heading2"><h2 id="Multiplicative_and_additive_functions">Multiplicative and additive functions</h2></div>

An arithmetic function a is

<ul><li><a href="Completely_additive_function" class="mw-redirect" title="Completely additive function">completely additive</a> if a(mn) = a(m) + a(n) for all natural numbers m and n;</li>

<li><a href="Completely_multiplicative_function" title="Completely multiplicative function">completely multiplicative</a> if a(1) = 1 and a(mn) = a(m)a(n) for all natural numbers m and n;</li></ul>

Two whole numbers m and n are called <a href="Coprime" class="mw-redirect" title="Coprime">coprime</a> if their <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> is 1, that is, if there is no <a href="Prime_number" title="Prime number">prime number</a> that divides both of them.

Then an arithmetic function a is

<ul><li><a href="Additive_function" title="Additive function">additive</a> if a(mn) = a(m) + a(n) for all coprime natural numbers m and n;</li>

<li><a href="Multiplicative_function" title="Multiplicative function">multiplicative</a> if a(1) = 1 and a(mn) = a(m)a(n) for all coprime natural numbers m and n.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notation">Notation</h2></div>

In this article, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{p}f(p)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{p}f(p)}</annotation>

</semantics>

</math><img src="./8bd85a3dda31b6726b12a87db448377418a61b69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.157ex; height:3.176ex;" alt="{\textstyle \sum _{p}f(p)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \prod _{p}f(p)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \prod _{p}f(p)}</annotation>

</semantics>

</math><img src="./58d3b6e7fad9ebeb1d75a1b70ea85d7a1fbfa93e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.897ex; height:3.176ex;" alt="{\textstyle \prod _{p}f(p)}" loading="lazy"> mean that the sum or product is over all <a href="Prime_number" title="Prime number">prime numbers</a>:

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{p}f(p)=f(2)+f(3)+f(5)+\cdots }</annotation>

</semantics>

</math>

and

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \prod _{p}f(p)=f(2)f(3)f(5)\cdots .}</annotation>

</semantics>

</math>

Similarly, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{p^{k}}f(p^{k})}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{p^{k}}f(p^{k})}</annotation>

</semantics>

</math><img src="./b20f60948d76e70734ed678e94e260efccd5a82e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.106ex; height:3.509ex;" alt="{\textstyle \sum _{p^{k}}f(p^{k})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \prod _{p^{k}}f(p^{k})}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \prod _{p^{k}}f(p^{k})}</annotation>

</semantics>

</math><img src="./c0c549506b3394feca47c5dc8156d7e28a08d275.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.846ex; height:3.509ex;" alt="{\textstyle \prod _{p^{k}}f(p^{k})}" loading="lazy"> mean that the sum or product is over all <a href="Prime_power" title="Prime power">prime powers</a> with strictly positive exponent (so k = 0 is not included):

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{p^{k}}f(p^{k})=\sum _{p}\sum _{k>0}f(p^{k})=f(2)+f(3)+f(4)+f(5)+f(7)+f(8)+f(9)+\cdots .}</annotation>

</semantics>

</math>

The notations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{d\mid n}f(d)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{d\mid n}f(d)}</annotation>

</semantics>

</math><img src="./5d887b2813d557e0ece1533421117a5e29358569.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.68ex; height:3.343ex;" alt="{\textstyle \sum _{d\mid n}f(d)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \prod _{d\mid n}f(d)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \prod _{d\mid n}f(d)}</annotation>

</semantics>

</math><img src="./7c0f6726c50025ee307be2442cac214dafd6e208.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.42ex; height:3.343ex;" alt="{\textstyle \prod _{d\mid n}f(d)}" loading="lazy"> mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if n = 12, then

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \prod _{d\mid 12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).}</annotation>

</semantics>

</math>

The notations can be combined: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{p\mid n}f(p)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{p\mid n}f(p)}</annotation>

</semantics>

</math><img src="./f841f75c84dcffa94290defc52a8e8aec89bde9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.601ex; height:3.343ex;" alt="{\textstyle \sum _{p\mid n}f(p)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \prod _{p\mid n}f(p)}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \prod _{p\mid n}f(p)}</annotation>

</semantics>

</math><img src="./bda77cc1126e6e1fdccda73dc229f04566319b06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:9.341ex; height:3.343ex;" alt="{\textstyle \prod _{p\mid n}f(p)}" loading="lazy"> mean that the sum or product is over all prime divisors of n. For example, if n = 18, then

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{p\mid 18}f(p)=f(2)+f(3),}</annotation>

</semantics>

</math>

and similarly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \sum _{p^{k}\mid n}f(p^{k})}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \sum _{p^{k}\mid n}f(p^{k})}</annotation>

</semantics>

</math><img src="./589ed8a50da8252e7632397c470aaf3c9a820eba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:11.549ex; height:3.509ex;" alt="{\textstyle \sum _{p^{k}\mid n}f(p^{k})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \prod _{p^{k}\mid n}f(p^{k})}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \prod _{p^{k}\mid n}f(p^{k})}</annotation>

</semantics>

</math><img src="./cb3cb47b03c4f3699dc9cc554565748eb55680b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:11.289ex; height:3.509ex;" alt="{\textstyle \prod _{p^{k}\mid n}f(p^{k})}" loading="lazy"> mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \prod _{p^{k}\mid 24}f(p^{k})=f(2)f(3)f(4)f(8).}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading2"><h2 id="Ω(n),_ω(n),_νp(n)_–_prime_power_decomposition">Ω(n), ω(n), νp(n) – prime power decomposition</h2></div>

The <a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">fundamental theorem of arithmetic</a> states that any positive integer n can be represented uniquely as a product of powers of primes: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}}</annotation>

</semantics>

</math><img src="./d3a0b9fa24964d5354f56263c05bd4b3056ac9d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.224ex; height:3.176ex;" alt="{\displaystyle n=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}}" loading="lazy"> where p1 < p2 < ... < pk are primes and the aj are positive integers. (1 is given by the empty product.)

It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define the <a href="P-adic_valuation" title="P-adic valuation">p-adic valuation</a> νp(n) to be the exponent of the highest power of the prime p that divides n. That is, if p is one of the pi then νp(n) = ai, otherwise it is zero. Then

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\prod _{p}p^{\nu _{p}(n)}.}</annotation>

</semantics>

</math>

In terms of the above the <a href="Prime_omega_function" title="Prime omega function">prime omega functions</a> ω and Ω are defined by

/* start https://en.wikipedia.org/ */

.mw-parser-output .block-indent{padding-left:3em;padding-right:0;overflow:hidden}

/* end https://en.wikipedia.org/ */

</style><div class="block-indent" style="padding-left: 1.5em;">ω(n) = k,</div>

To avoid repetition, formulas for the functions listed in this article are, whenever possible, given in terms of n and the corresponding pi, ai, ω, and Ω.

<div class="mw-heading mw-heading2"><h2 id="Multiplicative_functions">Multiplicative functions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="σk(n),_τ(n),_d(n)_–_divisor_sums">σk(n), τ(n), d(n) – divisor sums</h3></div>

<a href="Divisor_function" title="Divisor function">σk(n)</a> is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.

σ1(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).

Since a positive number to the zero power is one, σ0(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{k}(n)=\prod _{i=1}^{\omega (n)}{\frac {p_{i}^{(a_{i}+1)k}-1}{p_{i}^{k}-1}}=\prod _{i=1}^{\omega (n)}\left(1+p_{i}^{k}+p_{i}^{2k}+\cdots +p_{i}^{a_{i}k}\right).}</annotation>

</semantics>

</math>

Setting k = 0 in the second product gives

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau (n)=d(n)=(1+a_{1})(1+a_{2})\cdots (1+a_{\omega (n)}).}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="φ(n)_–_Euler_totient_function">φ(n) – Euler totient function</h3></div>

<a href="Euler_totient_function" class="mw-redirect" title="Euler totient function">φ(n)</a>, the Euler totient function, is the number of positive integers not greater than n that are coprime to n.

</mrow>

</munder>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=n\left({\frac {p_{1}-1}{p_{1}}}\right)\left({\frac {p_{2}-1}{p_{2}}}\right)\cdots \left({\frac {p_{\omega (n)}-1}{p_{\omega (n)}}}\right).}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="Jk(n)_–_Jordan_totient_function">Jk(n) – Jordan totient function</h3></div>

<a href="Jordan_totient_function" class="mw-redirect" title="Jordan totient function">Jk(n)</a>, the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, φ(n) = J1(n).

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{k}(n)=n^{k}\prod _{p\mid n}\left(1-{\frac {1}{p^{k}}}\right)=n^{k}\left({\frac {p_{1}^{k}-1}{p_{1}^{k}}}\right)\left({\frac {p_{2}^{k}-1}{p_{2}^{k}}}\right)\cdots \left({\frac {p_{\omega (n)}^{k}-1}{p_{\omega (n)}^{k}}}\right).}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="μ(n)_–_Möbius_function">μ(n) – Möbius function</h3></div>

<a href="M%C3%B6bius_function" title="Möbius function">μ(n)</a>, the Möbius function, is important because of the <a href="M%C3%B6bius_inversion" class="mw-redirect" title="Möbius inversion">Möbius inversion</a> formula. See <a href="#Dirichlet_convolution">§ Dirichlet convolution</a>, below.

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu (n)={\begin{cases}(-1)^{\omega (n)}=(-1)^{\Omega (n)}&{\text{if }}\;\omega (n)=\Omega (n)\\0&{\text{if }}\;\omega (n)\neq \Omega (n).\end{cases}}}</annotation>

</semantics>

</math>

This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

<div class="mw-heading mw-heading3"><h3 id="τ(n)_–_Ramanujan_tau_function">τ(n) – Ramanujan tau function</h3></div>

<a href="Ramanujan_tau_function" title="Ramanujan tau function">τ(n)</a>, the Ramanujan tau function, is defined by its <a href="Generating_function" title="Generating function">generating function</a> identity:

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{n\geq 1}\tau (n)q^{n}=q\prod _{n\geq 1}(1-q^{n})^{24}.}</annotation>

</semantics>

</math>

Although it is hard to say exactly what "arithmetical property of n" it "expresses",<a href="#cite_note-7">[7]</a> (τ(n) is (2π)−12 times the nth Fourier coefficient in the <a href="Q-expansion" class="mw-redirect" title="Q-expansion">q-expansion</a> of the <a href="Modular_discriminant" class="mw-redirect" title="Modular discriminant">modular discriminant</a> function)<a href="#cite_note-8">[8]</a> it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σk(n) and rk(n) functions (because these are also coefficients in the expansion of <a href="Modular_form" title="Modular form">modular forms</a>).

<div class="mw-heading mw-heading3"><h3 id="cq(n)_–_Ramanujan's_sum">cq(n) – Ramanujan's sum</h3></div>

<a href="Ramanujan's_sum" title="Ramanujan's sum">cq(n)</a>, Ramanujan's sum, is the sum of the nth powers of the primitive qth <a href="Roots_of_unity" class="mw-redirect" title="Roots of unity">roots of unity</a>:

<msub>

</mrow>

</msub>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<msup>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{q}(n)=\sum _{\stackrel {1\leq a\leq q}{\gcd(a,q)=1}}e^{2\pi i{\tfrac {a}{q}}n}.}</annotation>

</semantics>

</math>

Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

<dl><dd>If q and r are coprime, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{q}(n)c_{r}(n)=c_{qr}(n).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{q}(n)c_{r}(n)=c_{qr}(n).}</annotation>

</semantics>

</math><img src="./595a92b25f2f0d803a228b73cd76908e610d6616.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.07ex; height:3.009ex;" alt="{\displaystyle c_{q}(n)c_{r}(n)=c_{qr}(n).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="ψ(n)_–_Dedekind_psi_function">ψ(n) – Dedekind psi function</h3></div>

The <a href="Dedekind_psi_function" title="Dedekind psi function">Dedekind psi function</a>, used in the theory of <a href="Modular_function" class="mw-redirect" title="Modular function">modular functions</a>, is defined by the formula

</mrow>

</mrow>

</munder>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right).}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading2"><h2 id="Completely_multiplicative_functions">Completely multiplicative functions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="λ(n)_–_Liouville_function">λ(n) – Liouville function</h3></div>

<a href="Liouville_function" title="Liouville function">λ(n)</a>, the Liouville function, is defined by

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)=(-1)^{\Omega (n)}.}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="χ(n)_–_characters">χ(n) – characters</h3></div>

All <a href="Dirichlet_character" title="Dirichlet character">Dirichlet characters</a> χ(n) are completely multiplicative. Two characters have special notations:

The principal character (mod n) is denoted by χ0(a) (or χ1(a)). It is defined as

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{0}(a)={\begin{cases}1&{\text{if }}\gcd(a,n)=1,\\0&{\text{if }}\gcd(a,n)\neq 1.\end{cases}}}</annotation>

</semantics>

</math>

The quadratic character (mod n) is denoted by the <a href="Jacobi_symbol" title="Jacobi symbol">Jacobi symbol</a> for odd n (it is not defined for even n):

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{a_{1}}\left({\frac {a}{p_{2}}}\right)^{a_{2}}\cdots \left({\frac {a}{p_{\omega (n)}}}\right)^{a_{\omega (n)}}.}</annotation>

</semantics>

</math>

In this formula <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\tfrac {a}{p}})}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ({\tfrac {a}{p}})}</annotation>

</semantics>

</math><img src="./6ebb252decd96b7adf4d3fffdda2c15b718c7420.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:3.515ex; height:3.343ex;" alt="{\displaystyle ({\tfrac {a}{p}})}" loading="lazy"> is the <a href="Legendre_symbol" title="Legendre symbol">Legendre symbol</a>, defined for all integers a and all odd primes p by

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

<mtext> and for some integer </mtext>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>if there is no such </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{if }}a\equiv 0{\pmod {p}},\\+1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x,\;a\equiv x^{2}{\pmod {p}}\\-1&{\text{if there is no such }}x.\end{cases}}}</annotation>

</semantics>

</math>

Following the normal convention for the empty product, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left({\frac {a}{1}}\right)=1.}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{1}}\right)=1.}</annotation>

</semantics>

</math><img src="./8ab68e93d279e8d82d1153662b5aeb056dbcd50e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.749ex; height:4.843ex;" alt="{\displaystyle \left({\frac {a}{1}}\right)=1.}" loading="lazy">

<div class="mw-heading mw-heading2"><h2 id="Additive_functions">Additive functions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="ω(n)_–_distinct_prime_divisors">ω(n) – distinct prime divisors</h3></div>

ω(n), defined above as the number of distinct primes dividing n, is additive (see <a href="Prime_omega_function" title="Prime omega function">Prime omega function</a>).

<div class="mw-heading mw-heading2"><h2 id="Completely_additive_functions">Completely additive functions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Ω(n)_–_prime_divisors">Ω(n) – prime divisors</h3></div>

<a href="Prime_factor" class="mw-redirect" title="Prime factor">Ω(n)</a>, defined above as the number of prime factors of n counted with multiplicities, is completely additive (see <a href="Prime_omega_function" title="Prime omega function">Prime omega function</a>).

<div class="mw-heading mw-heading3"><h3 id="νp(n)_–_p-adic_valuation_of_an_integer_n">νp(n) – <a href="P-adic_valuation" title="P-adic valuation">p-adic valuation</a> of an integer n</h3></div>

For a fixed prime p, νp(n), defined above as the exponent of the largest power of p dividing n, is completely additive.

<div class="mw-heading mw-heading3"><h3 id="Logarithmic_derivative">Logarithmic derivative</h3></div>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mover>

<mtext> prime</mtext>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {ld} (n)={\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}}</annotation>

</semantics>

</math><img src="./d9106364adaeeee7c32f691abcdcf476845f0737.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.171ex; width:29.441ex; height:9.009ex;" alt="{\displaystyle \operatorname {ld} (n)={\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(n)}</annotation>

</semantics>

</math><img src="./c770d316f90c97bc02eb0813fe986be35b37f623.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.128ex; height:2.843ex;" alt="{\displaystyle D(n)}" loading="lazy"> is the arithmetic derivative.

<div class="mw-heading mw-heading2"><h2 id="Neither_multiplicative_nor_additive">Neither multiplicative nor additive</h2></div>

<div class="mw-heading mw-heading3"><h3 id="π(x),_Π(x),_ϑ(x),_ψ(x)_–_prime-counting_functions">π(x), Π(x), ϑ(x), ψ(x) – prime-counting functions</h3></div>

These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of the <a href="Prime_number_theorem" title="Prime number theorem">prime number theorem</a>. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

π(x), the <a href="Prime-counting_function" title="Prime-counting function">prime-counting function</a>, is the number of primes not exceeding x. It is the summation function of the <a href="Indicator_function" title="Indicator function">characteristic function</a> of the prime numbers.

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi (x)=\sum _{p\leq x}1}</annotation>

</semantics>

</math>

A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, etc. It is the summation function of the arithmetic function which takes the value 1/k on integers which are the kth power of some prime number, and the value 0 on other integers.

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi (x)=\sum _{p^{k}\leq x}{\frac {1}{k}}.}</annotation>

</semantics>

</math>

ϑ(x) and ψ(x), the <a href="Chebyshev_function" title="Chebyshev function">Chebyshev functions</a>, are defined as sums of the natural logarithms of the primes not exceeding x.

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vartheta (x)=\sum _{p\leq x}\log p,}</annotation>

</semantics>

</math>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \psi (x)=\sum _{p^{k}\leq x}\log p.}</annotation>

</semantics>

</math>

The second Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.

<div class="mw-heading mw-heading3"><h3 id="Λ(n)_–_von_Mangoldt_function">Λ(n) – von Mangoldt function</h3></div>

<a href="Von_Mangoldt_function" title="Von Mangoldt function">Λ(n)</a>, the von Mangoldt function, is 0 unless the argument n is a prime power pk, in which case it is the natural logarithm of the prime p:

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

<mtext> is a prime power</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<mtext> is not a prime power</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Lambda (n)={\begin{cases}\log p&{\text{if }}n=2,3,4,5,7,8,9,11,13,16,\ldots =p^{k}{\text{ is a prime power}}\\0&{\text{if }}n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;{\text{ is not a prime power}}.\end{cases}}}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="p(n)_–_partition_function">p(n) – partition function</h3></div>

<a href="Partition_function_(number_theory)" title="Partition function (number theory)">p(n)</a>, the partition function, is the number of ways of representing n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:

<mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(n)=\left|\left\{(a_{1},a_{2},\dots a_{k}):0<a_{1}\leq a_{2}\leq \cdots \leq a_{k}\;\land \;n=a_{1}+a_{2}+\cdots +a_{k}\right\}\right|.}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="λ(n)_–_Carmichael_function">λ(n) – Carmichael function</h3></div>

<a href="Carmichael_function" title="Carmichael function">λ(n)</a>, the Carmichael function, is the smallest positive number such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}</annotation>

</semantics>

</math><img src="./2e475506bcb72caae57599e0ccafa7efe023be9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.026ex; height:3.343ex;" alt="{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}" loading="lazy">   for all a coprime to n. Equivalently, it is the <a href="Least_common_multiple" title="Least common multiple">least common multiple</a> of the orders of the elements of the <a href="Multiplicative_group_of_integers_modulo_n" title="Multiplicative group of integers modulo n">multiplicative group of integers modulo n</a>.

For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n:

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)={\begin{cases}\;\;\phi (n)&{\text{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\phi (n)&{\text{if }}n=8,16,32,64,\dots \end{cases}}}</annotation>

</semantics>

</math>

and for general n it is the least common multiple of λ of each of the prime power factors of n:

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}})=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="h(n)_–_class_number">h(n) – class number</h3></div>

<a href="Ideal_class_group" title="Ideal class group">h(n)</a>, the class number function, is the order of the <a href="Ideal_class_group" title="Ideal class group">ideal class group</a> of an algebraic extension of the rationals with <a href="Discriminant" title="Discriminant">discriminant</a> n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See <a href="Quadratic_field" title="Quadratic field">quadratic field</a> and <a href="Cyclotomic_field" title="Cyclotomic field">cyclotomic field</a> for classical examples.

<div class="mw-heading mw-heading3"><h3 id="rk(n)_–_sum_of_k_squares">rk(n) – sum of k squares</h3></div>

<a href="Sum_of_squares_function" title="Sum of squares function">rk(n)</a> is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k}(n)=\left|\left\{(a_{1},a_{2},\dots ,a_{k}):n=a_{1}^{2}+a_{2}^{2}+\cdots +a_{k}^{2}\right\}\right|}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="D(n)_–_Arithmetic_derivative">D(n) – Arithmetic derivative</h3></div>

Using the <a href="Differential_operator#Notations" title="Differential operator">Heaviside notation</a> for the derivative, the <a href="Arithmetic_derivative" title="Arithmetic derivative">arithmetic derivative</a> D(n) is a function such that

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(n)=1}</annotation>

</semantics>

</math><img src="./533ce40a13f694e6b4a4440e252a6dbf8dd27e6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.389ex; height:2.843ex;" alt="{\displaystyle D(n)=1}" loading="lazy"> if n prime, and</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(mn)=mD(n)+D(m)n}</annotation>

</semantics>

</math><img src="./8a4693d4e5c85471a85a6f7129fae02722d8f790.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.445ex; height:2.843ex;" alt="{\displaystyle D(mn)=mD(n)+D(m)n}" loading="lazy"> (the <a href="Product_rule" title="Product rule">product rule</a>)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Summation_functions">Summation functions</h2></div>

Given an arithmetic function a(n), its summation function A(x) is defined by

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x):=\sum _{n\leq x}a(n).}</annotation>

</semantics>

</math>

A can be regarded as a function of a real variable. Given a positive integer m, A is constant along <a href="Open_interval" class="mw-redirect" title="Open interval">open intervals</a> m < x < m + 1, and has a <a href="Classification_of_discontinuities" title="Classification of discontinuities">jump discontinuity</a> at each integer for which a(m) ≠ 0.

Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

</munder>

</mrow>

</munder>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{0}(m):={\frac {1}{2}}\left(\sum _{n<m}a(n)+\sum _{n\leq m}a(n)\right)=A(m)-{\frac {1}{2}}a(m).}</annotation>

</semantics>

</math>

Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to find <a href="Asymptotic_analysis" title="Asymptotic analysis">asymptotic behaviour</a> for the summation function for large x.

A classical example of this phenomenon<a href="#cite_note-9">[9]</a> is given by the <a href="Divisor_summatory_function" title="Divisor summatory function">divisor summatory function</a>, the summation function of d(n), the number of divisors of n:

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \liminf _{n\to \infty }d(n)=2}</annotation>

</semantics>

</math>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \limsup _{n\to \infty }{\frac {\log d(n)\log \log n}{\log n}}=\log 2}</annotation>

</semantics>

</math>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{n\to \infty }{\frac {d(1)+d(2)+\cdots +d(n)}{\log(1)+\log(2)+\cdots +\log(n)}}=1.}</annotation>

</semantics>

</math>

An <a href="Average_order_of_an_arithmetic_function" title="Average order of an arithmetic function">average order of an arithmetic function</a> is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average". We say that g is an average order of f if

</mrow>

</munder>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{n\leq x}f(n)\sim \sum _{n\leq x}g(n)}</annotation>

</semantics>

</math>

as x tends to infinity. The example above shows that d(n) has the average order log(n).<a href="#cite_note-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Dirichlet_convolution">Dirichlet convolution</h2></div>

Given an arithmetic function a(n), let Fa(s), for complex s, be the function defined by the corresponding <a href="Dirichlet_series" title="Dirichlet series">Dirichlet series</a> (where it <a href="Convergent_series" title="Convergent series">converges</a>):<a href="#cite_note-11">[11]</a>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{a}(s):=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}.}</annotation>

</semantics>

</math>

Fa(s) is called a <a href="Generating_function" title="Generating function">generating function</a> of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ζ(s) the <a href="Riemann_zeta_function" title="Riemann zeta function">Riemann zeta function</a>.

The generating function of the Möbius function is the inverse of the zeta function:

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \zeta (s)\,\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}=1,\;\;\Re s>1.}</annotation>

</semantics>

</math>

Consider two arithmetic functions a and b and their respective generating functions Fa(s) and Fb(s). The product Fa(s)Fb(s) can be computed as follows:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{a}(s)F_{b}(s)=\left(\sum _{m=1}^{\infty }{\frac {a(m)}{m^{s}}}\right)\left(\sum _{n=1}^{\infty }{\frac {b(n)}{n^{s}}}\right).}</annotation>

</semantics>

</math>

It is a straightforward exercise to show that if c(n) is defined by

</mrow>

</munder>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(n):=\sum _{ij=n}a(i)b(j)=\sum _{i\mid n}a(i)b\left({\frac {n}{i}}\right),}</annotation>

</semantics>

</math>

then <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{c}(s)=F_{a}(s)F_{b}(s).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{c}(s)=F_{a}(s)F_{b}(s).}</annotation>

</semantics>

</math>

This function c is called the <a href="Dirichlet_convolution" title="Dirichlet convolution">Dirichlet convolution</a> of a and b, and is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a*b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a*b}</annotation>

</semantics>

</math><img src="./4baddb0eb2fc85a456316d026699d38f5166a27c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.422ex; height:2.176ex;" alt="{\displaystyle a*b}" loading="lazy">.

A particularly important case is convolution with the constant function a(n) = 1 for all n, corresponding to multiplying the generating function by the zeta function:

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(n)=\sum _{d\mid n}f(d).}</annotation>

</semantics>

</math>

Multiplying by the inverse of the zeta function gives the <a href="M%C3%B6bius_inversion" class="mw-redirect" title="Möbius inversion">Möbius inversion</a> formula:

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)g(d).}</annotation>

</semantics>

</math>

If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.

<div class="mw-heading mw-heading2"><h2 id="Relations_among_the_functions">Relations among the functions</h2></div>

There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The page <a href="Divisor_sum_identities" title="Divisor sum identities">divisor sum identities</a> contains many more generalized and related examples of identities involving arithmetic functions.

Here are a few examples:

<div class="mw-heading mw-heading3"><h3 id="Dirichlet_convolutions">Dirichlet convolutions</h3></div>

</mrow>

</munder>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left({\frac {n}{\delta }}\right)|\mu (\delta )|={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}n\neq 1\end{cases}}}</annotation>

</semantics>

</math><img src="./92e0d45e029769bb70bf1b00ce7585cf80df68a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:44.204ex; height:7.176ex;" alt="{\displaystyle \sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left({\frac {n}{\delta }}\right)|\mu (\delta )|={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}n\neq 1\end{cases}}}" loading="lazy">     where λ is the Liouville function.<a href="#cite_note-12">[12]</a></dd>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}\varphi (\delta )=n.}</annotation>

</semantics>

</math><img src="./4747cb524ca27051585361750fd2f475018ae6e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:13.26ex; height:6.009ex;" alt="{\displaystyle \sum _{\delta \mid n}\varphi (\delta )=n.}" loading="lazy">      <a href="#cite_note-13">[13]</a>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta =n\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta }}.}</annotation>

</semantics>

</math><img src="./6dd7ed8fc4415cfb18c568039a0c31a4817e6123.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:34.161ex; height:7.343ex;" alt="{\displaystyle \varphi (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta =n\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta }}.}" loading="lazy">       Möbius inversion</dd></dl></dd>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{d\mid n}J_{k}(d)=n^{k}.}</annotation>

</semantics>

</math><img src="./ee52b935c557a3a42d067e19663f04956554fcb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:15.375ex; height:6.009ex;" alt="{\displaystyle \sum _{d\mid n}J_{k}(d)=n^{k}.}" loading="lazy">      <a href="#cite_note-14">[14]</a>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J_{k}(n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta ^{k}=n^{k}\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta ^{k}}}.}</annotation>

</semantics>

</math><img src="./9f70c931813907149c78ac25d7ed9346987778c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:37.202ex; height:7.343ex;" alt="{\displaystyle J_{k}(n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta ^{k}=n^{k}\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta ^{k}}}.}" loading="lazy">       Möbius inversion</dd></dl></dd>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)}</annotation>

</semantics>

</math><img src="./cb8c2db0c42fa862a0af3d3e38b9ded07d93744d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:29.224ex; height:6.509ex;" alt="{\displaystyle \sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)}" loading="lazy">      <a href="#cite_note-15">[15]</a></dd>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}\varphi (\delta )d\left({\frac {n}{\delta }}\right)=\sigma (n).}</annotation>

</semantics>

</math><img src="./49a525e146f9b24dbc2cb6a06f40b94a2294d0f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:23.008ex; height:6.509ex;" alt="{\displaystyle \sum _{\delta \mid n}\varphi (\delta )d\left({\frac {n}{\delta }}\right)=\sigma (n).}" loading="lazy">      <a href="#cite_note-16">[16]</a><a href="#cite_note-17">[17]</a></dd>

</mrow>

</munder>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.}</annotation>

</semantics>

</math><img src="./79a189c4a8b0dab99c54bc4280c264411d73ffa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:17.723ex; height:6.009ex;" alt="{\displaystyle \sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.}" loading="lazy">      <a href="#cite_note-18">[18]</a>

</mrow>

</mrow>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\mu (n)|=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)2^{\omega (\delta )}.}</annotation>

</semantics>

</math><img src="./87ce1639e9cea2089b01979b3a1e6516993bfa06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:25.007ex; height:6.509ex;" alt="{\displaystyle |\mu (n)|=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)2^{\omega (\delta )}.}" loading="lazy">       Möbius inversion</dd></dl></dd>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}2^{\omega (\delta )}=d(n^{2}).}</annotation>

</semantics>

</math><img src="./0498744ecde08bb3bb17ee1c0ed1c74ab2033033.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:17.399ex; height:6.009ex;" alt="{\displaystyle \sum _{\delta \mid n}2^{\omega (\delta )}=d(n^{2}).}" loading="lazy">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{\omega (n)}=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d(\delta ^{2}).}</annotation>

</semantics>

</math><img src="./03747222207859a9a16cedf7b848d3e6f64cc0f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:24.485ex; height:6.509ex;" alt="{\displaystyle 2^{\omega (n)}=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d(\delta ^{2}).}" loading="lazy">       Möbius inversion</dd></dl></dd>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}d(\delta ^{2})=d^{2}(n).}</annotation>

</semantics>

</math><img src="./9778b40f0cb5d0fe110dc243b36c787d9ef08872.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:18.097ex; height:6.009ex;" alt="{\displaystyle \sum _{\delta \mid n}d(\delta ^{2})=d^{2}(n).}" loading="lazy">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(n^{2})=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d^{2}(\delta ).}</annotation>

</semantics>

</math><img src="./34891e7581650786b5f374f5df94cdbd64c6028e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:25.274ex; height:6.509ex;" alt="{\displaystyle d(n^{2})=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d^{2}(\delta ).}" loading="lazy">       Möbius inversion</dd></dl></dd>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}d\left({\frac {n}{\delta }}\right)2^{\omega (\delta )}=d^{2}(n).}</annotation>

</semantics>

</math><img src="./30d21683269fc00e2f9a1fbaeddc8056ae1af6b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:24.398ex; height:6.509ex;" alt="{\displaystyle \sum _{\delta \mid n}d\left({\frac {n}{\delta }}\right)2^{\omega (\delta )}=d^{2}(n).}" loading="lazy">      </dd>

</mrow>

</munder>

<mrow>

<mtr>

<mtd>

</mrow>

<mtext> is a square </mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<mtext> is not square.</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}\lambda (\delta )={\begin{cases}&1{\text{ if }}n{\text{ is a square }}\\&0{\text{ if }}n{\text{ is not square.}}\end{cases}}}</annotation>

</semantics>

</math><img src="./1af9b94306343af862e481d6dfc35d9bfc39ad74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:35.383ex; height:7.176ex;" alt="{\displaystyle \sum _{\delta \mid n}\lambda (\delta )={\begin{cases}&1{\text{ if }}n{\text{ is a square }}\\&0{\text{ if }}n{\text{ is not square.}}\end{cases}}}" loading="lazy">     where λ is the <a href="Liouville_function" title="Liouville function">Liouville function</a>.</dd>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}\Lambda (\delta )=\log n.}</annotation>

</semantics>

</math><img src="./012125cf76df22198a69c2bdb04aee25633e797a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:16.712ex; height:6.009ex;" alt="{\displaystyle \sum _{\delta \mid n}\Lambda (\delta )=\log n.}" loading="lazy">      <a href="#cite_note-19">[19]</a>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Lambda (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\log(\delta ).}</annotation>

</semantics>

</math><img src="./daab588acc3657cd0ea29db2037fa505cdb0844f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:25.316ex; height:6.509ex;" alt="{\displaystyle \Lambda (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\log(\delta ).}" loading="lazy">       Möbius inversion</dd></dl></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Sums_of_squares">Sums of squares</h3></div>

For all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq 4,\;\;\;r_{k}(n)>0.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\geq 4,\;\;\;r_{k}(n)>0.}</annotation>

</semantics>

</math><img src="./269ac99fb630e3d8788c4b686e91a191945264fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.691ex; height:2.843ex;" alt="{\displaystyle k\geq 4,\;\;\;r_{k}(n)>0.}" loading="lazy">     (<a href="Lagrange's_four-square_theorem" title="Lagrange's four-square theorem">Lagrange's four-square theorem</a>).

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{2}(n)=4\sum _{d\mid n}\left({\frac {-4}{d}}\right),}</annotation>

</semantics>

</math><img src="./ee7a257b4a5ab77994423a51b6c01940a694be7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:21.959ex; height:7.176ex;" alt="{\displaystyle r_{2}(n)=4\sum _{d\mid n}\left({\frac {-4}{d}}\right),}" loading="lazy"> <a href="#cite_note-20">[20]</a></dd></dl>

where the <a href="Kronecker_symbol" title="Kronecker symbol">Kronecker symbol</a> has the values

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {-4}{n}}\right)={\begin{cases}+1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\\\;\;\;0&{\text{if }}n{\text{ is even}}.\\\end{cases}}}</annotation>

</semantics>

</math><img src="./11735759c3837e661938c47d6f4178d6231ac878.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:35.715ex; height:8.509ex;" alt="{\displaystyle \left({\frac {-4}{n}}\right)={\begin{cases}+1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\\\;\;\;0&{\text{if }}n{\text{ is even}}.\\\end{cases}}}" loading="lazy"></dd></dl>

There is a formula for r3 in the section on <a href="#Class_number_related">class numbers</a> below.

<msub>

</mrow>

</msub>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{4}(n)=8\sum _{\stackrel {d\mid n}{4\,\nmid \,d}}d=8(2+(-1)^{n})\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d={\begin{cases}8\sigma (n)&{\text{if }}n{\text{ is odd }}\\24\sigma \left({\frac {n}{2^{\nu }}}\right)&{\text{if }}n{\text{ is even }}\end{cases}},}</annotation>

</semantics>

</math>

where ν = ν2(n).    <a href="#cite_note-21">[21]</a><a href="#cite_note-22">[22]</a><a href="#cite_note-23">[23]</a>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{6}(n)=16\sum _{d\mid n}\chi \left({\frac {n}{d}}\right)d^{2}-4\sum _{d\mid n}\chi (d)d^{2},}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi (n)=\left({\frac {-4}{n}}\right).}">

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi (n)=\left({\frac {-4}{n}}\right).}</annotation>

</semantics>

</math><img src="./c5fd20a9c253ad6e121c59cb1419ed35a591cf0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.019ex; height:6.176ex;" alt="{\displaystyle \chi (n)=\left({\frac {-4}{n}}\right).}" loading="lazy"><a href="#cite_note-Hardy_&_Wright,_§_20.13-24">[24]</a>

Define the function σk*(n) as<a href="#cite_note-25">[25]</a>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{k}^{*}(n)=(-1)^{n}\sum _{d\mid n}(-1)^{d}d^{k}={\begin{cases}\sum _{d\mid n}d^{k}=\sigma _{k}(n)&{\text{if }}n{\text{ is odd }}\\\sum _{\stackrel {d\mid n}{2\,\mid \,d}}d^{k}-\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d^{k}&{\text{if }}n{\text{ is even}}.\end{cases}}}</annotation>

</semantics>

</math>

That is, if n is odd, σk*(n) is the sum of the kth powers of the divisors of n, that is, σk(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{8}(n)=16\sigma _{3}^{*}(n).}</annotation>

</semantics>

</math><img src="./bb5a38accb4a48b27b02ad4332b58fea946340ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.966ex; height:3.009ex;" alt="{\displaystyle r_{8}(n)=16\sigma _{3}^{*}(n).}" loading="lazy">    <a href="#cite_note-Hardy_&_Wright,_§_20.13-24">[24]</a><a href="#cite_note-26">[26]</a></dd></dl>

Adopt the convention that Ramanujan's τ(x) = 0 if x is not an integer.

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</msubsup>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{24}(n)={\frac {16}{691}}\sigma _{11}^{*}(n)+{\frac {128}{691}}\left\{(-1)^{n-1}259\tau (n)-512\tau \left({\frac {n}{2}}\right)\right\}}</annotation>

</semantics>

</math><img src="./368f517b29e9a55b6a794e87448326cf681f0be7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:59.525ex; height:5.176ex;" alt="{\displaystyle r_{24}(n)={\frac {16}{691}}\sigma _{11}^{*}(n)+{\frac {128}{691}}\left\{(-1)^{n-1}259\tau (n)-512\tau \left({\frac {n}{2}}\right)\right\}}" loading="lazy">    <a href="#cite_note-27">[27]</a></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Divisor_sum_convolutions">Divisor sum convolutions</h3></div>

Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the <a href="Power_series#Multiplication_and_division" title="Power series">product of two power series</a>:

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\sum _{n=0}^{\infty }a_{n}x^{n}\right)\left(\sum _{n=0}^{\infty }b_{n}x^{n}\right)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }a_{i}b_{j}x^{i+j}=\sum _{n=0}^{\infty }\left(\sum _{i=0}^{n}a_{i}b_{n-i}\right)x^{n}=\sum _{n=0}^{\infty }c_{n}x^{n}.}</annotation>

</semantics>

</math><img src="./7c42331b3594b2fc84929158ecb40abc3b01b8d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:79.151ex; height:7.676ex;" alt="{\displaystyle \left(\sum _{n=0}^{\infty }a_{n}x^{n}\right)\left(\sum _{n=0}^{\infty }b_{n}x^{n}\right)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }a_{i}b_{j}x^{i+j}=\sum _{n=0}^{\infty }\left(\sum _{i=0}^{n}a_{i}b_{n-i}\right)x^{n}=\sum _{n=0}^{\infty }c_{n}x^{n}.}" loading="lazy"></dd></dl>

The sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}}</annotation>

</semantics>

</math><img src="./4c4f8c28943bb2755333b7664fec446e8ef9b198.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.157ex; height:6.843ex;" alt="{\displaystyle c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}}" loading="lazy"> is called the <a href="Convolution" title="Convolution">convolution</a> or the <a href="Cauchy_product" title="Cauchy product">Cauchy product</a> of the sequences an and bn.

These formulas may be proved analytically (see <a href="Eisenstein_series" title="Eisenstein series">Eisenstein series</a>) or by elementary methods.<a href="#cite_note-28">[28]</a>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.}</annotation>

</semantics>

</math><img src="./29fc43a8a78eae6518a69965bd29f51bb3f24f8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:58.619ex; height:7.509ex;" alt="{\displaystyle \sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.}" loading="lazy">    <a href="#cite_note-Ramanujan,_p._146-29">[29]</a></dd>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.}</annotation>

</semantics>

</math><img src="./ef679c37f53505899efb2f332faf2b9c22ffef8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:69.081ex; height:7.509ex;" alt="{\displaystyle \sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.}" loading="lazy">    <a href="#cite_note-Koblitz,_ex._III.2.8-30">[30]</a></dd>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}}</annotation>

</semantics>

</math><img src="./60804e1d6ff542e7aa015bfedd88cad618e4dbb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.005ex; width:68.799ex; height:13.176ex;" alt="{\displaystyle {\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}}" loading="lazy">    <a href="#cite_note-Koblitz,_ex._III.2.8-30">[30]</a><a href="#cite_note-31">[31]</a></dd>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}}</annotation>

</semantics>

</math><img src="./ba426096859105e768bfe3356f779f57518fce15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.005ex; width:68.799ex; height:15.176ex;" alt="{\displaystyle {\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}}" loading="lazy">    <a href="#cite_note-Ramanujan,_p._146-29">[29]</a><a href="#cite_note-32">[32]</a></dd>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),}</annotation>

</semantics>

</math><img src="./63f715859ad8220fb82516e61358dece84f74c22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:59.831ex; height:6.509ex;" alt="{\displaystyle \tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),}" loading="lazy">     where τ(n) is Ramanujan's function.    <a href="#cite_note-33">[33]</a><a href="#cite_note-34">[34]</a></dd></dl>

Since σk(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences<a href="#cite_note-35">[35]</a> for the functions. See <a href="Ramanujan_tau_function" title="Ramanujan tau function">Ramanujan tau function</a> for some examples.

Extend the domain of the partition function by setting p(0) = 1.

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(n)={\frac {1}{n}}\sum _{1\leq k\leq n}\sigma (k)p(n-k).}</annotation>

</semantics>

</math><img src="./669758ab94018ba29ad8c3e4c6f1d2ba757bd8d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; margin-left: -0.089ex; width:29.21ex; height:6.676ex;" alt="{\displaystyle p(n)={\frac {1}{n}}\sum _{1\leq k\leq n}\sigma (k)p(n-k).}" loading="lazy">    <a href="#cite_note-36">[36]</a>   This recurrence can be used to compute p(n).</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Class_number_related">Class number related</h3></div>

<a href="Peter_Gustav_Lejeune_Dirichlet" title="Peter Gustav Lejeune Dirichlet">Peter Gustav Lejeune Dirichlet</a> discovered formulas that relate the class number h of <a href="Quadratic_number_field" class="mw-redirect" title="Quadratic number field">quadratic number fields</a> to the Jacobi symbol.<a href="#cite_note-37">[37]</a>

An integer D is called a fundamental discriminant if it is the <a href="Discriminant" title="Discriminant">discriminant</a> of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is <a href="Squarefree" class="mw-redirect" title="Squarefree">squarefree</a> and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4).<a href="#cite_note-38">[38]</a>

Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the <a href="Kronecker_symbol" title="Kronecker symbol">Kronecker symbol</a>:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</msup>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {a}{2}}\right)={\begin{cases}\;\;\,0&{\text{ if }}a{\text{ is even}}\\(-1)^{\frac {a^{2}-1}{8}}&{\text{ if }}a{\text{ is odd. }}\end{cases}}}</annotation>

</semantics>

</math>

Then if D < −4 is a fundamental discriminant<a href="#cite_note-39">[39]</a><a href="#cite_note-40">[40]</a>

<mtr>

<mtd>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}h(D)&={\frac {1}{D}}\sum _{r=1}^{|D|}r\left({\frac {D}{r}}\right)\\&={\frac {1}{2-\left({\tfrac {D}{2}}\right)}}\sum _{r=1}^{|D|/2}\left({\frac {D}{r}}\right).\end{aligned}}}</annotation>

</semantics>

</math>

There is also a formula relating r3 and h. Again, let D be a fundamental discriminant, D < −4. Then<a href="#cite_note-41">[41]</a>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{3}(|D|)=12\left(1-\left({\frac {D}{2}}\right)\right)h(D).}</annotation>

</semantics>

</math>

<div class="mw-heading mw-heading3"><h3 id="Prime-count_related">Prime-count related</h3></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}</annotation>

</semantics>

</math><img src="./be2447b1119dfedd79acffdaf38c884e041cc4e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:27.723ex; height:5.176ex;" alt="{\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}" loading="lazy">   be the nth <a href="Harmonic_number" title="Harmonic number">harmonic number</a>. Then

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma (n)\leq H_{n}+e^{H_{n}}\log H_{n}}</annotation>

</semantics>

</math><img src="./46213fe5a0a864edea08701f6685418e9a7ca63c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.164ex; height:3.176ex;" alt="{\displaystyle \sigma (n)\leq H_{n}+e^{H_{n}}\log H_{n}}" loading="lazy">   is true for every natural number n if and only if the <a href="Riemann_hypothesis" title="Riemann hypothesis">Riemann hypothesis</a> is true.    <a href="#cite_note-42">[42]</a></dd></dl>

The Riemann hypothesis is also equivalent to the statement that, for all n > 5040,

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma (n)<e^{\gamma }n\log \log n}</annotation>

</semantics>

</math> (where γ is the <a href="Euler%E2%80%93Mascheroni_constant" class="mw-redirect" title="Euler–Mascheroni constant">Euler–Mascheroni constant</a>). This is <a href="Divisor_function#Growth_rate" title="Divisor function">Robin's theorem</a>.

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{p}\nu _{p}(n)=\Omega (n).}</annotation>

</semantics>

</math><img src="./8f0520c26d28903f0b2e17dac96ba768ee3c5a9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:17.781ex; height:5.676ex;" alt="{\displaystyle \sum _{p}\nu _{p}(n)=\Omega (n).}" loading="lazy"></dd>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \psi (x)=\sum _{n\leq x}\Lambda (n).}</annotation>

</semantics>

</math><img src="./4b9f73f28b91d91af2f0f8e927d24be3160d4f1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:16.957ex; height:5.676ex;" alt="{\displaystyle \psi (x)=\sum _{n\leq x}\Lambda (n).}" loading="lazy">    <a href="#cite_note-43">[43]</a></dd>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi (x)=\sum _{n\leq x}{\frac {\Lambda (n)}{\log n}}.}</annotation>

</semantics>

</math><img src="./87f09f36af683ce08ee290af00b923f4c2a74020.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:18.023ex; height:7.009ex;" alt="{\displaystyle \Pi (x)=\sum _{n\leq x}{\frac {\Lambda (n)}{\log n}}.}" loading="lazy">    <a href="#cite_note-44">[44]</a></dd>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{\theta (x)}=\prod _{p\leq x}p.}</annotation>

</semantics>

</math><img src="./d9cd8ef5619e6cbe18c811c9e67592f35841c798.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:12.654ex; height:5.843ex;" alt="{\displaystyle e^{\theta (x)}=\prod _{p\leq x}p.}" loading="lazy">    <a href="#cite_note-45">[45]</a></dd>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{\psi (x)}=\operatorname {lcm} [1,2,\dots ,\lfloor x\rfloor ].}</annotation>

</semantics>

</math><img src="./4f0671a33f6f269f9f767e7b72dc0383a7fc7c82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.191ex; height:3.343ex;" alt="{\displaystyle e^{\psi (x)}=\operatorname {lcm} [1,2,\dots ,\lfloor x\rfloor ].}" loading="lazy">    <a href="#cite_note-46">[46]</a></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Menon's_identity">Menon's identity</h3></div>

In 1965 <a href="P_Kesava_Menon" title="P Kesava Menon">P Kesava Menon</a> proved<a href="#cite_note-47">[47]</a>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n).}</annotation>

</semantics>

</math>

This has been generalized by a number of mathematicians. For example,

<mover>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mover>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},n)=1}}\gcd(k_{1}-1,k_{2},\dots ,k_{s},n)=\varphi (n)\sigma _{s-1}(n).}</annotation>

</semantics>

</math></li>

<mover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mover>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},k_{2},\dots ,k_{s},n)=1}}\gcd(k_{1}-a_{1},k_{2}-a_{2},\dots ,k_{s}-a_{s},n)^{s}=J_{s}(n)d(n),}</annotation>

</semantics>

</math> where a1, a2, ..., as are integers, gcd(a1, a2, ..., as, n) = 1.</li>

<li><a href="L%C3%A1szl%C3%B3_Fejes_T%C3%B3th" title="László Fejes Tóth">László Fejes Tóth</a><a href="#cite_note-50">[50]</a> <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{\stackrel {1\leq k\leq m}{\gcd(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},}">

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<mover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mover>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\stackrel {1\leq k\leq m}{\gcd(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},}</annotation>

</semantics>

</math> where m1 and m2 are odd, m = lcm(m1, m2).</li></ul>

In fact, if f is any arithmetical function<a href="#cite_note-51">[51]</a><a href="#cite_note-52">[52]</a>

<mover>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}f(\gcd(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}},}</annotation>

</semantics>

</math>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle *}</annotation>

</semantics>

</math><img src="./8e9972f426d9e07855984f73ee195a21dbc21755.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.079ex; margin-bottom: -0.25ex; width:1.162ex; height:1.509ex;" alt="{\displaystyle *}" loading="lazy"> stands for Dirichlet convolution.

<div class="mw-heading mw-heading3"><h3 id="Miscellaneous">Miscellaneous</h3></div>

Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of <a href="Quadratic_reciprocity" title="Quadratic reciprocity">quadratic reciprocity</a>:

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{(m-1)(n-1)/4}.}</annotation>

</semantics>

</math>

Let D(n) be the arithmetic derivative. Then the logarithmic derivative <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}.}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mover>

<mtext> prime</mtext>

</mrow>

</mrow>

</mover>

</mrow>

</munder>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}.}</annotation>

</semantics>

</math> See <a href="Arithmetic_derivative" title="Arithmetic derivative">Arithmetic derivative</a> for details.

Let λ(n) be Liouville's function. Then

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),}</annotation>

</semantics>

</math><img src="./e83d50f3e87c51707740040fe9988b5d7aace06e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.367ex; height:2.843ex;" alt="{\displaystyle |\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),}" loading="lazy">     and</dd>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)\mu (n)=|\mu (n)|=\mu ^{2}(n).}</annotation>

</semantics>

</math><img src="./84426eeb26447a1ec2ab04401ae74a5ae82ff22b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.568ex; height:3.176ex;" alt="{\displaystyle \lambda (n)\mu (n)=|\mu (n)|=\mu ^{2}(n).}" loading="lazy">    </dd></dl>

Let λ(n) be Carmichael's function. Then

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)\mid \phi (n).}</annotation>

</semantics>

</math><img src="./e2f9778d573cb65f9f60016068a0ac0ea9ccb6e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.733ex; height:2.843ex;" alt="{\displaystyle \lambda (n)\mid \phi (n).}" loading="lazy">     Further,</dd>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

<mtext>, where </mtext>

</mrow>

<mtext> is an odd prime)</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msup>

</mrow>

</msup>

<mtext>, where </mtext>

</mrow>

<mtext> is an odd prime)</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda (n)=\phi (n){\text{ if and only if }}n={\begin{cases}1,2,4;\\3,5,7,9,11,\ldots {\text{ (that is, }}p^{k}{\text{, where }}p{\text{ is an odd prime)}};\\6,10,14,18,\ldots {\text{ (that is, }}2p^{k}{\text{, where }}p{\text{ is an odd prime)}}.\end{cases}}}</annotation>

</semantics>

</math><img src="./1700918ad857c4e5f2a7eb54445e2785e50e5bcf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:87.563ex; height:8.843ex;" alt="{\displaystyle \lambda (n)=\phi (n){\text{ if and only if }}n={\begin{cases}1,2,4;\\3,5,7,9,11,\ldots {\text{ (that is, }}p^{k}{\text{, where }}p{\text{ is an odd prime)}};\\6,10,14,18,\ldots {\text{ (that is, }}2p^{k}{\text{, where }}p{\text{ is an odd prime)}}.\end{cases}}}" loading="lazy"></dd></dl>

See <a href="Multiplicative_group_of_integers_modulo_n" title="Multiplicative group of integers modulo n">Multiplicative group of integers modulo n</a> and <a href="Primitive_root_modulo_n" title="Primitive root modulo n">Primitive root modulo n</a>.

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}.}</annotation>

</semantics>

</math><img src="./83f2ddab8590b6372bfdb32df3dc74545c872223.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.793ex; height:3.343ex;" alt="{\displaystyle 2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}.}" loading="lazy">    <a href="#cite_note-53">[53]</a><a href="#cite_note-54">[54]</a></dd>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\phi (n)\sigma (n)}{n^{2}}}<1.}</annotation>

</semantics>

</math><img src="./557acffb6f82d40cae6ae4369f2c63769e4bb8ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:21.19ex; height:6.009ex;" alt="{\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\phi (n)\sigma (n)}{n^{2}}}<1.}" loading="lazy">    <a href="#cite_note-55">[55]</a></dd>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}c_{q}(n)&={\frac {\mu \left({\frac {q}{\gcd(q,n)}}\right)}{\phi \left({\frac {q}{\gcd(q,n)}}\right)}}\phi (q)\\&=\sum _{\delta \mid \gcd(q,n)}\mu \left({\frac {q}{\delta }}\right)\delta .\end{aligned}}}</annotation>

</semantics>

</math><img src="./ec4c2fd999f96339479e40edc3e5421374f8aa19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.838ex; width:25.495ex; height:16.843ex;" alt="{\displaystyle {\begin{aligned}c_{q}(n)&={\frac {\mu \left({\frac {q}{\gcd(q,n)}}\right)}{\phi \left({\frac {q}{\gcd(q,n)}}\right)}}\phi (q)\\&=\sum _{\delta \mid \gcd(q,n)}\mu \left({\frac {q}{\delta }}\right)\delta .\end{aligned}}}" loading="lazy">    <a href="#cite_note-56">[56]</a>     Note that  <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .}">

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .}</annotation>

</semantics>

</math><img src="./4856244f844fd39211f9653b7a9bb77c4adc0ecb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:19.657ex; height:6.509ex;" alt="{\displaystyle \phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .}" loading="lazy">    <a href="#cite_note-57">[57]</a></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{q}(1)=\mu (q).}</annotation>

</semantics>

</math><img src="./1baad8c1e5bc91763239fc1282a55ed73e8b324f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.993ex; height:3.009ex;" alt="{\displaystyle c_{q}(1)=\mu (q).}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{q}(q)=\phi (q).}</annotation>

</semantics>

</math><img src="./999756644a94b7440e6d2eb3ee47b4b8cf69769f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.884ex; height:3.009ex;" alt="{\displaystyle c_{q}(q)=\phi (q).}" loading="lazy"></dd>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{\delta \mid n}d^{3}(\delta )=\left(\sum _{\delta \mid n}d(\delta )\right)^{2}.}</annotation>

</semantics>

</math><img src="./615395bc95821e3397f18af1020b02377b33b552.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:25.555ex; height:8.676ex;" alt="{\displaystyle \sum _{\delta \mid n}d^{3}(\delta )=\left(\sum _{\delta \mid n}d(\delta )\right)^{2}.}" loading="lazy">    <a href="#cite_note-58">[58]</a>   Compare this with 13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2</dd>

</mrow>

</munder>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(uv)=\sum _{\delta \mid \gcd(u,v)}\mu (\delta )d\left({\frac {u}{\delta }}\right)d\left({\frac {v}{\delta }}\right).}</annotation>

</semantics>

</math><img src="./e81ad86fba6b2eac770597516167249f373d22ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:34.674ex; height:6.509ex;" alt="{\displaystyle d(uv)=\sum _{\delta \mid \gcd(u,v)}\mu (\delta )d\left({\frac {u}{\delta }}\right)d\left({\frac {v}{\delta }}\right).}" loading="lazy">    <a href="#cite_note-59">[59]</a></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<mrow>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{k}(u)\sigma _{k}(v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{k}\sigma _{k}\left({\frac {uv}{\delta ^{2}}}\right).}</annotation>

</semantics>

</math><img src="./63ed3429afd4bc31d042c4f6a62bab8d04fe19cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:34.227ex; height:7.176ex;" alt="{\displaystyle \sigma _{k}(u)\sigma _{k}(v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{k}\sigma _{k}\left({\frac {uv}{\delta ^{2}}}\right).}" loading="lazy">    <a href="#cite_note-60">[60]</a></dd>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<mrow>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau (u)\tau (v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{11}\tau \left({\frac {uv}{\delta ^{2}}}\right),}</annotation>

</semantics>

</math><img src="./fe65c15e16eb3d465e012cc7678a014b15fba9b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:31.372ex; height:7.176ex;" alt="{\displaystyle \tau (u)\tau (v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{11}\tau \left({\frac {uv}{\delta ^{2}}}\right),}" loading="lazy">     where τ(n) is Ramanujan's function.    <a href="#cite_note-61">[61]</a></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="First_100_values_of_some_arithmetic_functions">First 100 values of some arithmetic functions</h2></div>

<th>factorization</th>

<th>r4(n)

</th></tr>

<tr>

<td>8

</td></tr>

<td>24

</td></tr>

<td>32

</td></tr>

<tr>

<td>24

</td></tr>

<td>48

</td></tr>

<tr>

<td>96

</td></tr>

<td>64

</td></tr>

<tr>

<td>24

</td></tr>

<tr>

<td>104

</td></tr>

<tr>

<td>144

</td></tr>

<td>96

</td></tr>

<tr>

<td>96

</td></tr>

<td>112

</td></tr>

<tr>

<td>192

</td></tr>

<tr>

<td>192

</td></tr>

<tr>

<td>24

</td></tr>

<td>144

</td></tr>

<tr>

<td>312

</td></tr>

<td>160

</td></tr>

<tr>

<td>144

</td></tr>

<tr>

<td>256

</td></tr>

<tr>

<td>288

</td></tr>

<td>192

</td></tr>

<tr>

<td>96

</td></tr>

<tr>

<td>248

</td></tr>

<tr>

<td>336

</td></tr>

<tr>

<td>320

</td></tr>

<tr>

<td>192

</td></tr>

<td>240

</td></tr>

<tr>

<td>576

</td></tr>

<td>256

</td></tr>

<tr>

<td>24

</td></tr>

<tr>

<td>384

</td></tr>

<tr>

<td>432

</td></tr>

<tr>

<td>384

</td></tr>

<tr>

<td>312

</td></tr>

<td>304

</td></tr>

<tr>

<td>480

</td></tr>

<tr>

<td>448

</td></tr>

<tr>

<td>144

</td></tr>

<td>336

</td></tr>

<tr>

<td>768

</td></tr>

<td>352

</td></tr>

<tr>

<td>288

</td></tr>

<tr>

<td>624

</td></tr>

<tr>

<td>576

</td></tr>

<td>384

</td></tr>

<tr>

<td>96

</td></tr>

<tr>

<td>456

</td></tr>

<tr>

<td>744

</td></tr>

<tr>

<td>576

</td></tr>

<tr>

<td>336

</td></tr>

<td>432

</td></tr>

<tr>

<td>960

</td></tr>

<tr>

<td>576

</td></tr>

<tr>

<td>192

</td></tr>

<tr>

<td>640

</td></tr>

<tr>

<td>720

</td></tr>

<td>480

</td></tr>

<tr>

<td>576

</td></tr>

<td>496

</td></tr>

<tr>

<td>768

</td></tr>

<tr>

<td>832

</td></tr>

<tr>

<td>24

</td></tr>

<tr>

<td>672

</td></tr>

<tr>

<td>1152

</td></tr>

<td>544

</td></tr>

<tr>

<td>432

</td></tr>

<tr>

<td>768

</td></tr>

<tr>

<td>1152

</td></tr>

<td>576

</td></tr>

<tr>

<td>312

</td></tr>

<td>592

</td></tr>

<tr>

<td>912

</td></tr>

<tr>

<td>992

</td></tr>

<tr>

<td>480

</td></tr>

<tr>

<td>768

</td></tr>

<tr>

<td>1344

</td></tr>

<td>640

</td></tr>

<tr>

<td>144

</td></tr>

<tr>

<td>968

</td></tr>

<tr>

<td>1008

</td></tr>

<td>672

</td></tr>

<tr>

<td>768

</td></tr>

<tr>

<td>864

</td></tr>

<tr>

<td>1056

</td></tr>

<tr>

<td>960

</td></tr>

<tr>

<td>288

</td></tr>

<td>720

</td></tr>

<tr>

<td>1872

</td></tr>

<tr>

<td>896

</td></tr>

<tr>

<td>576

</td></tr>

<tr>

<td>1024

</td></tr>

<tr>

<td>1152

</td></tr>

<tr>

<td>960

</td></tr>

<tr>

<td>96

</td></tr>

<td>784

</td></tr>

<tr>

<td>1368

</td></tr>

<tr>

<td>1248

</td></tr>

<tr>

<td>744

</td></tr>

<tr>

<th>factorization</th>

<th>r4(n)

</th></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFLong1972">Long (1972</a>, p. 151)

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a href="#CITEREFPettofrezzoByrkit1970">Pettofrezzo & Byrkit (1970</a>, p. 58)

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Niven & Zuckerman, 4.2.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Nagell, I.9.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Bateman & Diamond, 2.1.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Hardy & Wright, intro. to Ch. XVI

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> Hardy, Ramanujan, § 10.2

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Hardy & Wright, §§ 18.1–18.2

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGérald_Tenenbaum1995" class="citation book cs1">Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. pp. 36–55. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-41261-7</bdi>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> Hardy & Wright, Thm. 263

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> Hardy & Wright, Thm. 63

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> see references at <a href="Jordan's_totient_function" title="Jordan's totient function">Jordan's totient function</a>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> Holden et al. in external links The formula is Gegenbauer's

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> Hardy & Wright, Thm. 288–290

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> Dineva in external links, prop. 4

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> Hardy & Wright, Thm. 264

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> Hardy & Wright, Thm. 296

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> Hardy & Wright, Thm. 278

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> Hardy & Wright, Thm. 386

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> Hardy, Ramanujan, eqs 9.1.2, 9.1.3

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> Koblitz, Ex. III.5.2

</li>

<li id="cite_note-Hardy_&_Wright,_§_20.13-24">^ <a href="#cite_ref-Hardy_&_Wright,_§_20.13_24-0">a</a> <a href="#cite_ref-Hardy_&_Wright,_§_20.13_24-1">b</a> Hardy & Wright, § 20.13

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> Hardy, Ramanujan, § 9.7

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> Hardy, Ramanujan, § 9.13

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> Hardy, Ramanujan, § 9.17

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> Williams, ch. 13; Huard, et al. (external links).

</li>

<li id="cite_note-Ramanujan,_p._146-29">^ <a href="#cite_ref-Ramanujan,_p._146_29-0">a</a> <a href="#cite_ref-Ramanujan,_p._146_29-1">b</a> Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146

</li>

<li id="cite_note-Koblitz,_ex._III.2.8-30">^ <a href="#cite_ref-Koblitz,_ex._III.2.8_30-0">a</a> <a href="#cite_ref-Koblitz,_ex._III.2.8_30-1">b</a> Koblitz, ex. III.2.8

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> Koblitz, ex. III.2.3

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> Koblitz, ex. III.2.2

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> Koblitz, ex. III.2.4

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> Apostol, Modular Functions ..., Ex. 6.10

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> Apostol, Modular Functions..., Ch. 6 Ex. 10

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279

</li>

<li id="cite_note-37"><a href="#cite_ref-37">^</a> Landau, p. 168, credits Gauss as well as Dirichlet

</li>

<li id="cite_note-38"><a href="#cite_ref-38">^</a> Cohen, Def. 5.1.2

</li>

<li id="cite_note-39"><a href="#cite_ref-39">^</a> Cohen, Corr. 5.3.13

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> see Edwards, § 9.5 exercises for more complicated formulas.

</li>

<li id="cite_note-41"><a href="#cite_ref-41">^</a> Cohen, Prop 5.3.10

</li>

<li id="cite_note-42"><a href="#cite_ref-42">^</a> See <a href="Divisor_function#Growth_rate" title="Divisor function">Divisor function</a>.

</li>

<li id="cite_note-43"><a href="#cite_ref-43">^</a> Hardy & Wright, eq. 22.1.2

</li>

<li id="cite_note-44"><a href="#cite_ref-44">^</a> See <a href="Prime-counting_function#Other_prime-counting_functions" title="Prime-counting function">prime-counting functions</a>.

</li>

<li id="cite_note-45"><a href="#cite_ref-45">^</a> Hardy & Wright, eq. 22.1.1

</li>

<li id="cite_note-46"><a href="#cite_ref-46">^</a> Hardy & Wright, eq. 22.1.3

</li>

<li id="cite_note-47"><a href="#cite_ref-47">^</a> László Tóth, Menon's Identity and Arithmetical Sums ..., eq. 1

</li>

<li id="cite_note-48"><a href="#cite_ref-48">^</a> Tóth, eq. 5

</li>

<li id="cite_note-49"><a href="#cite_ref-49">^</a> Tóth, eq. 3

</li>

<li id="cite_note-50"><a href="#cite_ref-50">^</a> Tóth, eq. 35

</li>

<li id="cite_note-51"><a href="#cite_ref-51">^</a> Tóth, eq. 2

</li>

<li id="cite_note-52"><a href="#cite_ref-52">^</a> Tóth states that Menon proved this for multiplicative f in 1965 and V. Sita Ramaiah for general f.

</li>

<li id="cite_note-53"><a href="#cite_ref-53">^</a> Hardy Ramanujan, eq. 3.10.3

</li>

<li id="cite_note-54"><a href="#cite_ref-54">^</a> Hardy & Wright, § 22.13

</li>

<li id="cite_note-55"><a href="#cite_ref-55">^</a> Hardy & Wright, Thm. 329

</li>

<li id="cite_note-56"><a href="#cite_ref-56">^</a> Hardy & Wright, Thms. 271, 272

</li>

<li id="cite_note-57"><a href="#cite_ref-57">^</a> Hardy & Wright, eq. 16.3.1

</li>

<li id="cite_note-58"><a href="#cite_ref-58">^</a> Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (C); Papers p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville.

</li>

<li id="cite_note-59"><a href="#cite_ref-59">^</a> Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p. 134

</li>

<li id="cite_note-60"><a href="#cite_ref-60">^</a> Apostol, Modular Functions ..., ch. 6 eq. 4

</li>

<li id="cite_note-61"><a href="#cite_ref-61">^</a> Apostol, Modular Functions ..., ch. 6 eq. 3

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFTom_M._Apostol1976" class="citation cs2"><a href="Tom_M._Apostol" title="Tom M. Apostol">Tom M. Apostol</a> (1976), <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoan00apos_0">Introduction to Analytic Number Theory</a>, Springer <a href="Undergraduate_Texts_in_Mathematics" title="Undergraduate Texts in Mathematics">Undergraduate Texts in Mathematics</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-90163-9</bdi></cite></li>

<li><cite id="CITEREFApostol1989" class="citation cs2"><a href="Tom_M._Apostol" title="Tom M. Apostol">Apostol, Tom M.</a> (1989), <a rel="nofollow" class="external text" href="https://archive.org/details/modularfunctions0000apos">Modular Functions and Dirichlet Series in Number Theory (2nd Edition)</a>, New York: Springer, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-97127-0</bdi></cite></li>

<li><cite id="CITEREFBatemanDiamond2004" class="citation cs2"><a href="Paul_T._Bateman" title="Paul T. Bateman">Bateman, Paul T.</a>; Diamond, Harold G. (2004), Analytic number theory, an introduction, <a href="World_Scientific" title="World Scientific">World Scientific</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-981-238-938-1</bdi></cite></li>

<li><cite id="CITEREFCohen1993" class="citation cs2"><a href="Henri_Cohen_(number_theorist)" title="Henri Cohen (number theorist)">Cohen, Henri</a> (1993), A Course in Computational Algebraic Number Theory, Berlin: <a href="Springer_Nature" title="Springer Nature">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-55640-0</bdi></cite></li>

<li><cite id="CITEREFEdwards1977" class="citation book cs1"><a href="Harold_Edwards_(mathematician)" title="Harold Edwards (mathematician)">Edwards, Harold</a> (1977). Fermat's Last Theorem. New York: <a href="Springer_Nature" title="Springer Nature">Springer</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-90230-9</bdi>.</cite></li>

<li><cite id="CITEREFHardy1999" class="citation cs2"><a href="G._H._Hardy" title="G. H. Hardy">Hardy, G. H.</a> (1999), Ramanujan: Twelve Lectures on Subjects Suggested by his Life and work, Providence RI: AMS / Chelsea, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10115%2F1436">10115/1436</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-2023-0</bdi></cite></li>

<li><cite id="CITEREFHardyWright1979" class="citation book cs1"><a href="G._H._Hardy" title="G. H. Hardy">Hardy, G. H.</a>; <a href="E._M._Wright" title="E. M. Wright">Wright, E. M.</a> (1979) [1938]. <a href="An_Introduction_to_the_Theory_of_Numbers" title="An Introduction to the Theory of Numbers">An Introduction to the Theory of Numbers</a> (5th ed.). Oxford: Clarendon Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-19-853171-0</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0568909">0568909</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0423.10001">0423.10001</a>.</cite></li>

<li><cite id="CITEREFJameson2003" class="citation cs2">Jameson, G. J. O. (2003), The Prime Number Theorem, Cambridge University Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-89110-8</bdi></cite></li>

<li><cite id="CITEREFKoblitz1984" class="citation cs2">Koblitz, Neal (1984), Introduction to Elliptic Curves and Modular Forms, New York: Springer, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-97966-2</bdi></cite></li>

<li><cite id="CITEREFLandau1966" class="citation cs2"><a href="Edmund_Landau" title="Edmund Landau">Landau, Edmund</a> (1966), Elementary Number Theory, New York: Chelsea</cite></li>

<li><cite id="CITEREFWilliam_J._LeVeque1996" class="citation cs2"><a href="William_J._LeVeque" title="William J. LeVeque">William J. LeVeque</a> (1996), Fundamentals of Number Theory, Courier Dover Publications, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-486-68906-9</bdi></cite></li>

<li><cite id="CITEREFLong1972" class="citation cs2">Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: <a href="D._C._Heath_and_Company" title="D. C. Heath and Company">D. C. Heath and Company</a>, <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/77-171950">77-171950</a></cite></li>

<li><cite id="CITEREFElliott_Mendelson1987" class="citation cs2">Elliott Mendelson (1987), Introduction to Mathematical Logic, CRC Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-412-80830-7</bdi></cite></li>

<li><cite id="CITEREFNagell1964" class="citation cs2"><a href="Trygve_Nagell" title="Trygve Nagell">Nagell, Trygve</a> (1964), Introduction to number theory (2nd Edition), Chelsea, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-2833-5</bdi></cite> <code class="cs1-code">{{citation}}</code>: ISBN / Date incompatibility (help)</li>

<li><cite id="CITEREFNivenZuckerman1972" class="citation cs2"><a href="Ivan_M._Niven" title="Ivan M. Niven">Niven, Ivan M.</a>; Zuckerman, Herbert S. (1972), An introduction to the theory of numbers (3rd Edition), <a href="John_Wiley_%26_Sons" class="mw-redirect" title="John Wiley & Sons">John Wiley & Sons</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-64154-5</bdi></cite></li>

<li><cite id="CITEREFPettofrezzoByrkit1970" class="citation cs2">Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: <a href="Prentice_Hall" title="Prentice Hall">Prentice Hall</a>, <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/77-81766">77-81766</a></cite></li>

<li><cite id="CITEREFRamanujan2000" class="citation cs2">Ramanujan, Srinivasa (2000), Collected Papers, Providence RI: AMS / Chelsea, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-2076-6</bdi></cite></li>

<li><cite id="CITEREFWilliams2011" class="citation cs2">Williams, Kenneth S. (2011), Number theory in the spirit of Liouville, London Mathematical Society Student Texts, vol. 76, Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-17562-3</bdi>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1227.11002">1227.11002</a></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFSchwarzSpilker1994" class="citation cs2">Schwarz, Wolfgang; Spilker, Jürgen (1994), Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties, London Mathematical Society Lecture Note Series, vol. 184, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-42725-8</bdi>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0807.11001">0807.11001</a></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Arithmetic_function">"Arithmetic function"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li>Matthew Holden, Michael Orrison, Michael Varble <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160305132124/https://www.math.hmc.edu/~orrison/research/papers/totient.pdf">Yet another Generalization of Euler's Totient Function</a></li>

<li>Huard, Ou, Spearman, and Williams. <a rel="nofollow" class="external text" href="http://mathstat.carleton.ca/~williams/papers/pdf/249.pdf">Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions</a></li>

<li>Dineva, Rosica, <a rel="nofollow" class="external text" href="http://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf">The Euler Totient, the Möbius, and the Divisor Functions</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210116061553/https://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf">Archived</a> 2021-01-16 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li>László Tóth, <a rel="nofollow" class="external text" href="https://arxiv.org/PS_cache/arxiv/pdf/1103/1103.5861v2.pdf">Menon's Identity and arithmetical sums representing functions of several variables</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Classes_of_natural_numbers743" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Classes_of_natural_numbers743" style="font-size:114%;margin:0 4em">Classes of <a href="Natural_number" title="Natural number">natural numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Powers_and_related_numbers743" style="font-size:114%;margin:0 4em"><a href="Exponentiation" title="Exponentiation">Powers</a> and related numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Achilles_number" title="Achilles number">Achilles</a></li>

<li><a href="Power_of_two" title="Power of two">Power of 2</a></li>

<li><a href="Power_of_three" title="Power of three">Power of 3</a></li>

<li><a href="Power_of_10" title="Power of 10">Power of 10</a></li>

<li><a href="Square_number" title="Square number">Square</a></li>

<li><a href="Fourth_power" title="Fourth power">Fourth power</a></li>

<li><a href="Fifth_power_(algebra)" title="Fifth power (algebra)">Fifth power</a></li>

<li><a href="Sixth_power" title="Sixth power">Sixth power</a></li>

<li><a href="Seventh_power" title="Seventh power">Seventh power</a></li>

<li><a href="Eighth_power" title="Eighth power">Eighth power</a></li>

<li><a href="Perfect_power" title="Perfect power">Perfect power</a></li>

<li><a href="Powerful_number" title="Powerful number">Powerful</a></li>

<li><a href="Prime_power" title="Prime power">Prime power</a></li></ul>

<ul><li><a href="Cullen_number" title="Cullen number">Cullen</a></li>

<li><a href="Double_Mersenne_number" title="Double Mersenne number">Double Mersenne</a></li>

<li><a href="Fermat_number" title="Fermat number">Fermat</a></li>

<li><a href="Mersenne_prime" title="Mersenne prime">Mersenne</a></li>

<li><a href="Proth_number" class="mw-redirect" title="Proth number">Proth</a></li>

<li><a href="Thabit_number" title="Thabit number">Thabit</a></li>

<li><a href="Woodall_number" title="Woodall number">Woodall</a></li></ul>

<ul><li><a href="Hilbert_number" title="Hilbert number">Hilbert</a></li>

<li><a href="Idoneal_number" title="Idoneal number">Idoneal</a></li>

<li><a href="Leyland_number" title="Leyland number">Leyland</a></li>

<li><a href="Loeschian_number" class="mw-redirect" title="Loeschian number">Loeschian</a></li>

<li><a href="Lucky_numbers_of_Euler" title="Lucky numbers of Euler">Lucky numbers of Euler</a></li></ul>

<ul><li><a href="Fibonacci_sequence" title="Fibonacci sequence">Fibonacci</a></li>

<li><a href="Jacobsthal_number" title="Jacobsthal number">Jacobsthal</a></li>

<li><a href="Leonardo_number" title="Leonardo number">Leonardo</a></li>

<li><a href="Lucas_number" title="Lucas number">Lucas</a></li>

<li><a href="Supergolden_ratio#Narayana_sequence" title="Supergolden ratio">Narayana</a></li>

<li><a href="Padovan_sequence" title="Padovan sequence">Padovan</a></li>

<li><a href="Perrin_number" title="Perrin number">Perrin</a></li></ul>

<ul><li><a href="Amenable_number" title="Amenable number">Amenable</a></li>

<li><a href="Congruent_number" title="Congruent number">Congruent</a></li>

<li><a href="Kn%C3%B6del_number" title="Knödel number">Knödel</a></li>

<li><a href="Riesel_number" title="Riesel number">Riesel</a></li>

<li><a href="Sierpi%C5%84ski_number" title="Sierpiński number">Sierpiński</a></li></ul>

<ul><li><a href="Nonhypotenuse_number" title="Nonhypotenuse number">Nonhypotenuse</a></li>

<li><a href="Polite_number" title="Polite number">Polite</a></li>

<li><a href="Practical_number" title="Practical number">Practical</a></li>

<li><a href="Primary_pseudoperfect_number" title="Primary pseudoperfect number">Primary pseudoperfect</a></li>

<li><a href="Wolstenholme_number" title="Wolstenholme number">Wolstenholme</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Figurate_numbers743" style="font-size:114%;margin:0 4em"><a href="Figurate_number" title="Figurate number">Figurate numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Plane_(mathematics)" title="Plane (mathematics)">2-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Centered_polygonal_number" title="Centered polygonal number">centered</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Centered_triangular_number" title="Centered triangular number">Centered triangular</a></li>

<li><a href="Centered_square_number" title="Centered square number">Centered square</a></li>

<li><a href="Centered_pentagonal_number" title="Centered pentagonal number">Centered pentagonal</a></li>

<li><a href="Centered_hexagonal_number" title="Centered hexagonal number">Centered hexagonal</a></li>

<li><a href="Centered_heptagonal_number" title="Centered heptagonal number">Centered heptagonal</a></li>

<li><a href="Centered_octagonal_number" title="Centered octagonal number">Centered octagonal</a></li>

<li><a href="Centered_nonagonal_number" title="Centered nonagonal number">Centered nonagonal</a></li>

<li><a href="Centered_decagonal_number" title="Centered decagonal number">Centered decagonal</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Polygonal_number" title="Polygonal number">non-centered</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Triangular_number" title="Triangular number">Triangular</a></li>

<li><a href="Square_number" title="Square number">Square</a></li>

<li><a href="Square_triangular_number" title="Square triangular number">Square triangular</a></li>

<li><a href="Pentagonal_number" title="Pentagonal number">Pentagonal</a></li>

<li><a href="Hexagonal_number" title="Hexagonal number">Hexagonal</a></li>

<li><a href="Heptagonal_number" title="Heptagonal number">Heptagonal</a></li>

<li><a href="Octagonal_number" title="Octagonal number">Octagonal</a></li>

<li><a href="Nonagonal_number" title="Nonagonal number">Nonagonal</a></li>

<li><a href="Decagonal_number" title="Decagonal number">Decagonal</a></li>

<li><a href="Dodecagonal_number" title="Dodecagonal number">Dodecagonal</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Three-dimensional_space" title="Three-dimensional space">3-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Centered_polyhedral_number" title="Centered polyhedral number">centered</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Centered_tetrahedral_number" title="Centered tetrahedral number">Centered tetrahedral</a></li>

<li><a href="Centered_cube_number" title="Centered cube number">Centered cube</a></li>

<li><a href="Centered_octahedral_number" title="Centered octahedral number">Centered octahedral</a></li>

<li><a href="Centered_dodecahedral_number" title="Centered dodecahedral number">Centered dodecahedral</a></li>

<li><a href="Centered_icosahedral_number" title="Centered icosahedral number">Centered icosahedral</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Polyhedral_number" class="mw-redirect" title="Polyhedral number">non-centered</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Tetrahedral_number" title="Tetrahedral number">Tetrahedral</a></li>

<li><a href="Cube_(algebra)" title="Cube (algebra)">Cubic</a></li>

<li><a href="Octahedral_number" title="Octahedral number">Octahedral</a></li>

<li><a href="Dodecahedral_number" title="Dodecahedral number">Dodecahedral</a></li>

<li><a href="Icosahedral_number" title="Icosahedral number">Icosahedral</a></li>

<li><a href="Stella_octangula_number" title="Stella octangula number">Stella octangula</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Pyramidal_number" title="Pyramidal number">pyramidal</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Square_pyramidal_number" title="Square pyramidal number">Square pyramidal</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Four-dimensional_space" title="Four-dimensional space">4-dimensional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">non-centered</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Pentatope_number" title="Pentatope number">Pentatope</a></li>

<li><a href="Squared_triangular_number" title="Squared triangular number">Squared triangular</a></li>

<li><a href="Fourth_power" title="Fourth power">Tesseractic</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial_numbers743" style="font-size:114%;margin:0 4em">Combinatorial numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Catalan_number" title="Catalan number">Catalan</a></li>

<li><a href="Dedekind_number" title="Dedekind number">Dedekind</a></li>

<li><a href="Delannoy_number" title="Delannoy number">Delannoy</a></li>

<li><a href="Euler_number" class="mw-redirect" title="Euler number">Euler</a></li>

<li><a href="Eulerian_number" title="Eulerian number">Eulerian</a></li>

<li><a href="Fuss%E2%80%93Catalan_number" title="Fuss–Catalan number">Fuss–Catalan</a></li>

<li><a href="Lazy_caterer's_sequence" title="Lazy caterer's sequence">Lazy caterer's sequence</a></li>

<li><a href="Motzkin_number" title="Motzkin number">Motzkin</a></li>

<li><a href="Narayana_number" title="Narayana number">Narayana</a></li>

<li><a href="Ordered_Bell_number" title="Ordered Bell number">Ordered Bell</a></li>

<li><a href="Schr%C3%B6der_number" title="Schröder number">Schröder</a></li>

<li><a href="Schr%C3%B6der%E2%80%93Hipparchus_number" title="Schröder–Hipparchus number">Schröder–Hipparchus</a></li>

<li><a href="Stirling_numbers_of_the_first_kind" title="Stirling numbers of the first kind">Stirling first</a></li>

<li><a href="Stirling_numbers_of_the_second_kind" title="Stirling numbers of the second kind">Stirling second</a></li>

<li><a href="Telephone_number_(mathematics)" title="Telephone number (mathematics)">Telephone number</a></li>

<li><a href="Wedderburn%E2%80%93Etherington_number" title="Wedderburn–Etherington number">Wedderburn–Etherington</a></li></ul>

<ul><li><a href="Wieferich_prime#Wieferich_numbers" title="Wieferich prime">Wieferich</a></li>

<li><a href="Wolstenholme_prime" title="Wolstenholme prime">Wolstenholme prime</a></li>

<li><a href="Wilson_prime#Wilson_numbers" title="Wilson prime">Wilson</a></li></ul>

<ul><li><a href="Carmichael_number" title="Carmichael number">Carmichael number</a></li>

<li><a href="Catalan_pseudoprime" title="Catalan pseudoprime">Catalan pseudoprime</a></li>

<li><a href="Elliptic_pseudoprime" title="Elliptic pseudoprime">Elliptic pseudoprime</a></li>

<li><a href="Euler_pseudoprime" title="Euler pseudoprime">Euler pseudoprime</a></li>

<li><a href="Euler%E2%80%93Jacobi_pseudoprime" title="Euler–Jacobi pseudoprime">Euler–Jacobi pseudoprime</a></li>

<li><a href="Fermat_pseudoprime" title="Fermat pseudoprime">Fermat pseudoprime</a></li>

<li><a href="Frobenius_pseudoprime" title="Frobenius pseudoprime">Frobenius pseudoprime</a></li>

<li><a href="Lucas_pseudoprime" title="Lucas pseudoprime">Lucas pseudoprime</a></li>

<li><a href="Lucas%E2%80%93Carmichael_number" title="Lucas–Carmichael number">Lucas–Carmichael number</a></li>

<li><a href="Perrin_number#Perrin_primality_test" title="Perrin number">Perrin pseudoprime</a></li>

<li><a href="Somer%E2%80%93Lucas_pseudoprime" title="Somer–Lucas pseudoprime">Somer–Lucas pseudoprime</a></li>

<li><a href="Strong_pseudoprime" title="Strong pseudoprime">Strong pseudoprime</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Arithmetic_functions_and_dynamics743" style="font-size:114%;margin:0 4em"> and <a href="Arithmetic_dynamics" title="Arithmetic dynamics">dynamics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Divisor_function" title="Divisor function">Divisor functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abundant_number" title="Abundant number">Abundant</a></li>

<li><a href="Almost_perfect_number" title="Almost perfect number">Almost perfect</a></li>

<li><a href="Arithmetic_number" title="Arithmetic number">Arithmetic</a></li>

<li><a href="Betrothed_numbers" title="Betrothed numbers">Betrothed</a></li>

<li><a href="Colossally_abundant_number" title="Colossally abundant number">Colossally abundant</a></li>

<li><a href="Deficient_number" title="Deficient number">Deficient</a></li>

<li><a href="Descartes_number" title="Descartes number">Descartes</a></li>

<li><a href="Hemiperfect_number" title="Hemiperfect number">Hemiperfect</a></li>

<li><a href="Highly_abundant_number" title="Highly abundant number">Highly abundant</a></li>

<li><a href="Highly_composite_number" title="Highly composite number">Highly composite</a></li>

<li><a href="Hyperperfect_number" title="Hyperperfect number">Hyperperfect</a></li>

<li><a href="Multiply_perfect_number" title="Multiply perfect number">Multiply perfect</a></li>

<li><a href="Perfect_number" title="Perfect number">Perfect</a></li>

<li><a href="Practical_number" title="Practical number">Practical</a></li>

<li><a href="Primitive_abundant_number" title="Primitive abundant number">Primitive abundant</a></li>

<li><a href="Quasiperfect_number" title="Quasiperfect number">Quasiperfect</a></li>

<li><a href="Refactorable_number" title="Refactorable number">Refactorable</a></li>

<li><a href="Semiperfect_number" title="Semiperfect number">Semiperfect</a></li>

<li><a href="Sublime_number" title="Sublime number">Sublime</a></li>

<li><a href="Superabundant_number" title="Superabundant number">Superabundant</a></li>

<li><a href="Superior_highly_composite_number" title="Superior highly composite number">Superior highly composite</a></li>

<li><a href="Superperfect_number" title="Superperfect number">Superperfect</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Prime_omega_function" title="Prime omega function">Prime omega functions</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Almost_prime" title="Almost prime">Almost prime</a></li>

<li><a href="Semiprime" title="Semiprime">Semiprime</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Euler's_totient_function" title="Euler's totient function">Euler's totient function</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Highly_cototient_number" title="Highly cototient number">Highly cototient</a></li>

<li><a href="Highly_totient_number" title="Highly totient number">Highly totient</a></li>

<li><a href="Noncototient" title="Noncototient">Noncototient</a></li>

<li><a href="Nontotient" title="Nontotient">Nontotient</a></li>

<li><a href="Perfect_totient_number" title="Perfect totient number">Perfect totient</a></li>

<li><a href="Sparsely_totient_number" title="Sparsely totient number">Sparsely totient</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Aliquot_sequence" title="Aliquot sequence">Aliquot sequences</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Amicable_numbers" title="Amicable numbers">Amicable</a></li>

<li><a href="Perfect_number" title="Perfect number">Perfect</a></li>

<li><a href="Sociable_numbers" class="mw-redirect" title="Sociable numbers">Sociable</a></li>

<li><a href="Untouchable_number" title="Untouchable number">Untouchable</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Primorial" title="Primorial">Primorial</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Euclid_number" title="Euclid number">Euclid</a></li>

<li><a href="Fortunate_number" title="Fortunate number">Fortunate</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Other_prime_factor_or_divisor_related_numbers743" style="font-size:114%;margin:0 4em">Other <a href="Prime_factor" class="mw-redirect" title="Prime factor">prime factor</a> or <a href="Divisor" title="Divisor">divisor</a> related numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Cyclic_number_(group_theory)" title="Cyclic number (group theory)">Cyclic</a></li>

<li><a href="Erd%C5%91s%E2%80%93Nicolas_number" title="Erdős–Nicolas number">Erdős–Nicolas</a></li>

<li><a href="Erd%C5%91s%E2%80%93Woods_number" title="Erdős–Woods number">Erdős–Woods</a></li>

<li><a href="Friendly_number" title="Friendly number">Friendly</a></li>

<li><a href="Giuga_number" title="Giuga number">Giuga</a></li>

<li><a href="Harmonic_divisor_number" title="Harmonic divisor number">Harmonic divisor</a></li>

<li><a href="Jordan%E2%80%93P%C3%B3lya_number" title="Jordan–Pólya number">Jordan–Pólya</a></li>

<li><a href="Lucas%E2%80%93Carmichael_number" title="Lucas–Carmichael number">Lucas–Carmichael</a></li>

<li><a href="Pronic_number" title="Pronic number">Pronic</a></li>

<li><a href="Regular_number" title="Regular number">Regular</a></li>

<li><a href="Rough_number" title="Rough number">Rough</a></li>

<li><a href="Smooth_number" title="Smooth number">Smooth</a></li>

<li><a href="Sphenic_number" title="Sphenic number">Sphenic</a></li>

<li><a href="St%C3%B8rmer_number" title="Størmer number">Størmer</a></li>

<li><a href="Super-Poulet_number" title="Super-Poulet number">Super-Poulet</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Numeral_system-dependent_numbers743" style="font-size:114%;margin:0 4em"><a href="Numeral_system" title="Numeral system">Numeral system</a>-dependent numbers</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"> and <a href="Arithmetic_dynamics" title="Arithmetic dynamics">dynamics</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Persistence_of_a_number" title="Persistence of a number">Persistence</a>

<ul><li><a href="Additive_persistence" class="mw-redirect" title="Additive persistence">Additive</a></li>

<li><a href="Multiplicative_persistence" class="mw-redirect" title="Multiplicative persistence">Multiplicative</a></li></ul></li></ul>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Digit_sum" title="Digit sum">Digit sum</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Digit_sum" title="Digit sum">Digit sum</a></li>

<li><a href="Digital_root" title="Digital root">Digital root</a></li>

<li><a href="Sum-product_number" title="Sum-product number">Sum-product</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Digit product</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multiplicative_digital_root" title="Multiplicative digital root">Multiplicative digital root</a></li>

<li><a href="Sum-product_number" title="Sum-product number">Sum-product</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coding-related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Meertens_number" title="Meertens number">Meertens</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dudeney_number" title="Dudeney number">Dudeney</a></li>

<li><a href="Factorion" title="Factorion">Factorion</a></li>

<li><a href="Kaprekar_number" title="Kaprekar number">Kaprekar</a></li>

<li><a href="Kaprekar's_routine" title="Kaprekar's routine">Kaprekar's constant</a></li>

<li><a href="Keith_number" title="Keith number">Keith</a></li>

<li><a href="Lychrel_number" title="Lychrel number">Lychrel</a></li>

<li><a href="Narcissistic_number" title="Narcissistic number">Narcissistic</a></li>

<li><a href="Perfect_digit-to-digit_invariant" title="Perfect digit-to-digit invariant">Perfect digit-to-digit invariant</a></li>

<li><a href="Perfect_digital_invariant" title="Perfect digital invariant">Perfect digital invariant</a>

<ul><li><a href="Happy_number" title="Happy number">Happy</a></li></ul></li></ul>

</div></td></tr></tbody></table><div>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="P-adic_numbers" class="mw-redirect" title="P-adic numbers">P-adic numbers</a>-related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automorphic_number" title="Automorphic number">Automorphic</a>

<ul><li><a href="Trimorphic_number" class="mw-redirect" title="Trimorphic number">Trimorphic</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Numerical_digit" title="Numerical digit">Digit</a>-composition related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Palindromic_number" title="Palindromic number">Palindromic</a></li>

<li><a href="Pandigital_number" title="Pandigital number">Pandigital</a></li>

<li><a href="Repdigit" title="Repdigit">Repdigit</a></li>

<li><a href="Repunit" title="Repunit">Repunit</a></li>

<li><a href="Self-descriptive_number" title="Self-descriptive number">Self-descriptive</a></li>

<li><a href="Smarandache%E2%80%93Wellin_number" title="Smarandache–Wellin number">Smarandache–Wellin</a></li>

<li><a href="Undulating_number" title="Undulating number">Undulating</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Digit-<a href="Permutation" title="Permutation">permutation</a> related</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cyclic_number" title="Cyclic number">Cyclic</a></li>

<li><a href="Digit-reassembly_number" title="Digit-reassembly number">Digit-reassembly</a></li>

<li><a href="Parasitic_number" title="Parasitic number">Parasitic</a></li>

<li><a href="Primeval_number" title="Primeval number">Primeval</a></li>

<li><a href="Transposable_integer" title="Transposable integer">Transposable</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Divisor-related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Equidigital_number" title="Equidigital number">Equidigital</a></li>

<li><a href="Extravagant_number" title="Extravagant number">Extravagant</a></li>

<li><a href="Frugal_number" title="Frugal number">Frugal</a></li>

<li><a href="Harshad_number" title="Harshad number">Harshad</a></li>

<li><a href="Polydivisible_number" title="Polydivisible number">Polydivisible</a></li>

<li><a href="Smith_number" title="Smith number">Smith</a></li>

<li><a href="Vampire_number" title="Vampire number">Vampire</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Friedman_number" title="Friedman number">Friedman</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Binary_numbers743" style="font-size:114%;margin:0 4em"><a href="Binary_number" title="Binary number">Binary numbers</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Odious_number" title="Odious number">Odious</a></li>

<li><a href="Pernicious_number" title="Pernicious number">Pernicious</a></li></ul>

<ul><li><a href="Lucky_number" title="Lucky number">Lucky</a></li>

<li><a href="Generation_of_primes" title="Generation of primes">Prime</a></li></ul>

<ul><li><a href="Pancake_sorting" title="Pancake sorting">Pancake number</a></li>

<li><a href="Sorting_number" title="Sorting number">Sorting number</a></li></ul>

<ul><li><a href="Aronson's_sequence" title="Aronson's sequence">Aronson's sequence</a></li>

<ul><li><a href="Strobogrammatic_number" title="Strobogrammatic number">Strobogrammatic</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2" style="font-weight:bold;"><div>

<ul><li> <a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox397" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://id.ndl.go.jp/auth/ndlna/00571752">Japan</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-06" href="https://en.wikipedia.org/wiki/?title=Arithmetic_function&oldid=1284175370">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>